package com.duoduo.动态规划;

import java.util.Arrays;

/**
 * @author dl.chai
 * @version 1.0
 * @description: 零钱兑换322
 * 给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。
 *
 * 计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。
 *
 * 你可以认为每种硬币的数量是无限的。
 *
 *
 *
 * 示例 1：
 *
 * 输入：coins = [1, 2, 5], amount = 11
 * 输出：3
 * 解释：11 = 5 + 5 + 1
 * 示例 2：
 *
 * 输入：coins = [2], amount = 3
 * 输出：-1
 * 示例 3：
 *
 * 输入：coins = [1], amount = 0
 * 输出：0
 * @date 2023/3/27 21:52
 */

public class 零钱兑换322 {
    public int coinChange2(int[] coins, int amount) {
        int max = amount + 1;
        // 初始化DP
        int[] dp=new int[amount+1];
        // 填充
        Arrays.fill(dp,max);
        dp[0]=0;
        //外层背包，内层物品      这个题其实反过来也行，我试了
        for(int i=1;i<=amount;i++){
            for(int j=0;j<coins.length;j++){
                // 当前值小于当前背包计算才有意义
                if(coins[j]<=i){
                    // dp[i-coins[j]]表示有一个数字10 再加1就11
                    //  或者9+2也是11，这里的加一和加二都是加一种数字，所以加一
                    dp[i]=Math.min(dp[i-coins[j]]+1,dp[i]);
                }
            }
        }
        return dp[amount]>amount?-1:dp[amount];
    }

    //f(x)=min(f(x-1),f(x-2)...）+1
    public int coinChange(int[] coins, int amount) {
        int max = Integer.MAX_VALUE;
        int[] dp = new int[amount + 1];
        //初始化dp数组为最大值
        Arrays.fill(dp,max);
        //当金额为0时需要的硬币数目为0
        dp[0] = 0;
        for (int i = 0; i < coins.length; i++) {
            //正序遍历：完全背包每个硬币可以选择多次
            for (int j = coins[i]; j <= amount; j++) {
                //只有dp[j-coins[i]]不是初始最大值时，该位才有选择的必要
                if (dp[j - coins[i]] != max) {
                    //选择硬币数目最小的情况
                    dp[j] = Math.min(dp[j], dp[j - coins[i]] + 1);
                }
            }
        }
        return dp[amount] == max ? -1 : dp[amount];
    }

    public static void main(String[] args) {
        int i = new 零钱兑换322().coinChange2(new int[]{2}, 3);
        System.out.println(i);
    }
}
